《经典算法大全》摘抄笔记整理

里面收录了51种常用算法，这里整理一些基础问题~

---

漏桶算法

一、限流：
每个API接口都是有访问上限的,当访问频率或者并发量超过其承受范围时候,我们就必须考虑限流来保证接口的可用性或者降级可用性.即接口也需要安装上保险丝,以防止非预期的请求对系统压力过大而引起的系统瘫痪.

通常的策略就是拒绝多余的访问,或者让多余的访问排队等待服务,或者引流.如果要准确的控制QPS,简单的做法是维护一个单位时间内的Counter,如判断单位时间已经过去,则将Counter重置零.此做法被认为没有很好的处理单位时间的边界,比如在前一秒的最后一毫秒里和下一秒的第一毫秒都触发了最大的请求数,将目光移动一下,就看到在两毫秒内发生了两倍的QPS.

二、限流算法：
常用的更平滑的限流算法有两种:漏桶算法和令牌桶算法.

漏桶算法的漏出速率是固定的参数,所以,即使网络中不存在资源冲突(没有发生拥塞),漏桶算法也不能使流突发(burst)到端口速率.因此,漏桶算法对于存在突发特性的流量来说缺乏效率.
漏桶可以看作是一个带有常量服务时间的单服务器队列，如果漏桶（包缓存）溢出，那么数据包会被丢弃。
在网络中，漏桶算法可以控制端口的流量输出速率，平滑网络上的突发流量，实现流量整形，从而为网络提供一个稳定的流量。

令牌桶算法(Token Bucket)和 Leaky Bucket 效果一样但方向相反的算法,更加容易理解.随着时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了就不再加了.新请求来临时,会各自拿走一个Token,如果没有Token可拿了就阻塞或者拒绝服务.

三、漏桶算法和令牌桶算法的区别
漏桶算法与令牌桶算法在表面看起来类似，很容易将两者混淆。但事实上，这两者具有截然不同的特性，且为不同的目的而使用。漏桶算法与令牌桶算法的区别在于：

1）漏桶算法能够强行限制数据的传输速率。
2）令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。

需要说明的是：在某些情况下，漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的，所以即使网络中没有发生拥塞，漏桶算法也不能使某一个单独的数据流达到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常，漏桶算法与令牌桶算法结合起来为网络流量提供更高效的控制。

一般背包问题

一般背包问题（背包问题）：如果物品是可以分割的，也就是允许将其中的一部分装入背包。

🌰：盗贼偷金粉
算法：贪心算法
（往一个杯子里放东西，先放石子，再放沙，最后水）

0/1背包问题

0/1背包问题：如果每一件物品不能分割，只能作为整体或者装入背包，或者不装入

🌰：盗贼偷金锭
算法：动态规划算法
（当决定是否放入i时，我们需要考虑两种子问题。
　　一：如果放入，那我们考虑在物品数为i-1， 背包容量为j-weight[i]时的价值
　　二：如果不放入，物品数为i-1， 重量为j时的价值
　　哪一个大，选择哪一个。）

解决思路：对于这种问题，我们可以采用一个二维数组去解决：f[i][j]，其中i代表加入背包的是前i件物品，j表示背包的承重，f[i][j]表示当前状态下能放进背包里面的物品的最大总价值。那么，f[n][m]就是我们的最终结果了。

采用动态规划，必须要知道初始状态和状态转移方程。初始状态很容易就能知道，那么状态转移方程如何求呢？对于一件物品，我们有放进或者不放进背包两种选择：
1)假如我们放进背包，f[i][j] = f[i - 1][j - weight[i]] + value[i]，这里的f[i - 1][j - weight[i]] + value[i]应该这么理解：在没放这件物品之前的状态值加上要放进去这件物品的价值。而对于f[i - 1][j - weight[i]]这部分，i - 1很容易理解，关键是 j - weight[i]这里，我们要明白：要把这件物品放进背包，就得在背包里面预留这一部分空间。
2)假如我们不放进背包，f[i][j] = f[i - 1][j]，这个很容易理解。
因此，我们的状态转移方程就是：f[i][j] = max(f[i][j] = f[i - 1][j] , f[i - 1][j - weight[i]] + value[i])
当然，还有一种特殊的情况，就是背包放不下当前这一件物品，这种情况下f[i][j] = f[i - 1][j]。

最佳合并模式

思路：
若要使得带权外路径长度最小，可以将权值大的节点尽量靠近根节点，这样路径短一些；而权值小的节点可以适当远离根节点，因为权值小，外路径稍微长一点也没事。

伪代码：
用一个优先权队列存储所有的初始节点；
从队列中选出两个权值最小的节点，将它们的和作为它们的根节点，并放入队列中；
循环这个过程，直到队列中只有一个节点为止，此时具有最小带权路径的扩充二叉树构造完毕！此时带权外路径长度即为最小的读写次数。

最小代价生成树

🌰：n个村庄间架设通信线路，每个村庄间的距离不同，如何架设最节省开销？

这个问题中，村庄可以抽象成节点，村庄之间的距离抽象成带权值的边，要求最节约的架设方案其实就是求如何使用最少的边、最小的权值和将图中所有的节点连接起来。
这就是一个最小代价生成树的问题，可以用Prim算法或kruskal算法解决。

PS1：无向连通图的生成树是一个极小连通子图。
PS2：生成树是图的一个子图，包括所有的顶点和最少的边（n-1条边）。
PS3：最小代价生成树就是所有生成树中权值之和最小的那个。

算法的目标很明确，就是要在n个节点的图中，找出n-1个节点，并且节点之间连线的权值是最小的。

迪杰斯特拉算法

一、描述：
迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止

二、基本思想
通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。

佛洛依德算法

一、算法的特点：
弗洛伊德算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或有向图或负权（但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。

二、算法的思路
通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入两个矩阵，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P中的元素b[i][j]，表示顶点i到顶点j经过了b[i][j]记录的值所表示的顶点。

假设图G中顶点个数为N，则需要对矩阵D和矩阵P进行N次更新。初始时，矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞，矩阵P的值为顶点b[i][j]的j的值。 接下来开始，对矩阵D进行N次更新。第1次更新时，如果”a[i][j]的距离” > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表示”i与j之间经过第1个顶点的距离”)，则更新a[i][j]为”a[i][0]+a[0][j]”,更新b[i][j]=b[i][0]。 同理，第k次更新时，如果”a[i][j]的距离” > “a[i][k-1]+a[k-1][j]”，则更新a[i][j]为”a[i][k-1]+a[k-1][j]”,b[i][j]=b[i][k-1]。更新N次之后，操作完成！

进程调度算法

需要进程调度的理由很简单，即充分利用计算机系统中的CPU资源，让计算机系统能够多快好省地完成我们让它做的各种任务。为此，可在内存中可存放数目远大于计算机系统内CPU个数的进程，让这些进程在操作系统的进程调度器的调度下，能够让进程高效（高的吞吐量–throughput）、及时（低延迟–latency）、公平（fairness）地使用CPU。

指标：
1）CPU利用率：CPU是计算机系统中的稀缺资源，所以应在有具体任务的情况下尽可能使CPU保持忙，从而使得CPU资源利用率最高。
2）吞吐量：CPU运行时的工作量大小是以每单位时间所完成的进程数目来描述的，即称为吞吐量。
3）周转时间：指从进程创建到作进程结束所经过的时间，这期间包括了由于各种因素（比如等待I/O操作完成）导致的进程阻塞，处于就绪态并在就绪队列中排队，在处理机上运行所花时间的总和。
4）等待时间：即进程在就绪队列中等待所花的时间总和。因此衡量一个调度算法的简单方法就是统计进程在就绪队列上的等待时间。
5）响应时间：指从事件（比如产生了一次时钟中断事件）产生到进程或系统作出响应所经过的时间。在交互式桌面计算机系统中，用户希望响应时间越快越好，但这常常要以牺牲吞吐量为代价。

最长公共子序列

一、区分
最长公共子串（Longest Common Substirng）和最长公共子序列（Longest Common Subsequence，LCS）的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。

二、应用
最长公共子序列的问题常用于解决字符串的相似度，是一个非常实用的算法
1）枚举法
2）动态规划法

多段图问题

多段图最短路径问题是应用动态规划的经典问题之一，许多优化问题都能转化为多段图最短路径问题进而求解。

问题求解：
采用自底向上的动态规划算法进行求解，先求解源s到第2阶段所有节点的最短路径，然后求第3阶段所有节点的最短路径，以此类推，直到求到汇节点。

1.从前往后依次给所有结点编号；序号必须从0开始，依次递增，同一阶段的结点顺序可以随意；
2.创建数组cost和d，分别记录每个结点的最短路径长度 和 每个结点最短路径的前驱结点；
3.从最后一个结点开始，从后向前，依次计算每个结点的cost值和d值；
4.直到将所有结点都计算完毕后，即可得到最短路径。

n皇后问题

问题：
N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。

广度优先搜索算法：
这里使用的是一个改良版的广度优先搜索算法。在N×N的棋盘上，我们先在第一行的第一个位置放置下皇后，接着我们就不去管第一行了，因为第一行已经不能放置皇后了。我们在第二行找到所有的可以放置皇后的位置。同理我们现在可以不用去管前两行了。我们对于第二行的每一个可以放置皇后的位置，都在第三行继续寻找可以放置皇后的位置，如此往复，直到我们遍历到最后一行。这个时候我们就得到了一部分解，这些解是对于第一个皇后放置在第一行第一列的位置而言。接下来对于第一行第二列、第三列…所有列都进行这个步骤，就得到了所有的解。

回溯算法：
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。这也是N皇后问题的传统解法，很经典。

广度优先搜索（宽度优先搜索） BFS

描述：
属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形：
1、把根节点放到队列的末尾。
2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
3、找到所要找的元素时结束程序。
4、如果遍历整个树还没有找到，结束程序。

深度优先搜索 DFS

描述：
其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.

深度优先搜索用栈（stack）来实现，整个过程可以想象成一个倒立的树形：
1、把根节点压入栈中。
2、每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。
3、找到所要找的元素时结束程序。
4、如果遍历整个树还没有找到，结束程序。

应用：
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。

递归和迭代

递归：程序调用自身称为递归
优点：大问题转化为小问题，可以减少代码量，同时代码精简，可读性好；
缺点：就是递归调用浪费了空间，而且递归太深容易造成堆栈的溢出。

迭代：利用变量的原值推出新值称为迭代
优点：就是代码运行效率好，因为时间只因循环次数增加而增加，而且没有额外的空间开销；
缺点：就是代码不如递归简洁

缓存淘汰算法

使用LRU(least-recently-used) 算法来淘汰（清理）使用频率较低的缓存。

缓存清理策略：
使用三个维度来标记，分别是count（缓存数量），cost（开销），age（距上一次的访问时间）。YYMemoryCache提供了分别针对这三个维度的清理缓存的接口。用户可以根据不同的需求（策略）来清理在某一维度超标的缓存。